1. Field of Invention
The present invention relates generally to prefetching and page replacement. More specifically, the present invention is related to a novel method for prefetching and page replacement based upon grouping nodes of hierarchical data into a plurality of regions.
2. Discussion of Prior Art
In transactional systems, finite amounts of pages (free pages) are allocated from memory to hold data from disks. When all free pages are used, that is when all pages contain valid data; when more pages are needed, then certain pages are chosen for replacement. The module that determines which pages to be replaced is the bufferpool component. The bufferpool component tries to keep frequently used pages in memory while replacing others by using well-known protocols. For example, it can try to replace the pages lease recently used in the system (LRU) or the pages most recently used in the system (MRU).
Bufferpool managers currently use a number of techniques in deciding which pages to replace in the system. One way, as shown in FIG. 1, is to use a clock pointer, which is an atomic variable that indexes into a circular array of page descriptors. Within the page descriptors is information that describes bufferpool pages, such as the pointer to the page, a fix count or reference count, description of the contents of the page, and a weight count. The weight count is assigned to a page when the system unfixes (unreferences) a page, and it reflects the probability of that page being referenced in the future. When the free page list is exhausted, the clock pointer is “moved” to point to the pages in the list in a clockwise fashion. While the clock pointer moves from one page descriptor to the next, it decrements the weight count in the current page descriptor. If the clock pointer encounters a page descriptor whose fixed count is zero and whose weight count is below a threshold value, it chooses that page for page replacement. Therefore, the higher weight count assigned to a page, the more likely the page will stay in memory in the bufferpool. Typically, the system assigns high weight counts to pages it knows will be referenced often, such as the root page of an index or a control page.
Another technique, as shown in FIG. 2, uses a linked list of page descriptors pointed to by a head pointer and a tail pointer. Pages are added to the linked list when they're unfixed. If the page is unlikely to be needed in the future, it is added to the head of the list. If it is likely to be referenced in the future, it is placed on the tail of the list. The next page to be replaced will be picked from the head of the list.
The following references provide for a general teaching with regard to page replacement, but they fail to provide for the claimed invention's robust method and system of page replacement in ordered nodes wherein the nodes are ordered into isolated regions.
U.S. patent application publication 2003/0018876 A1 provides for virtual memory mapping using region-based page tables, wherein a region register file provides a region identifier for a virtual address in a virtual memory space. The virtual address includes a virtual region number and a virtual page number. A virtual page table look-up circuit is coupled to the region register file to generate a page table entry (PTE) virtual address from virtual address parameters. The virtual address parameters include the virtual address.
U.S. Pat. No. 6,496,912 discloses a system, method, and software for memory management with intelligent trimming of pages of working sets. The computer system has memory space allocatable in chunks, known as pages, to specific application programs or processes. Also disclosed is a trimming method that estimates numbers of trimmable pages for working sets based upon a measure of how much time has elapsed since the memory pages were last accessed by the corresponding application program.
U.S. Pat. No. 6,473,840 discloses a data processing system having a network and method for managing memory by storing discardable pages in a local paging device. A discardable page that is to be removed from the memory is identified. A determination is made as to whether performance will increase by storing the discardable page in a paging device located within the data processing system. If it is determined that performance will increase, the discardable page is marked as a paged discardable page and stored in the paging device locally, wherein this page may be retrieved from the paging device. The paging device may take the form of a paging file, such as a swap file. If space is unavailable within the paging device, the discardable page may be discarded. These processes may be implemented in a network computer.
U.S. Pat. No. 6,408,368 discloses an operating system page placement to maximize cache data reuse. The operating system designates one or more pages containing critical data, text, or other digital information as hot pages within a physical system memory in the computer system and prevents replacement during execution of various application programs of these hot pages when cached. The operating system inhibits allocation of the conflict pages that would map to cache locations occupied by a cached hot page, thereby preserving the hot page within the cache memory. The conflict pages are placed at the bottom of a free list created in the system memory by the operating system. The operating system scans the free list using a pointer while allocating free system memory space at run-time. The system memory pages are allocated from the free list until the pointer reaches a conflict page. This allows the operating system to prevent the conflict pages from getting cached to the hot page location within the cache memory.
U.S. Pat. No. 6,408,364 describes an apparatus and method for implementing a least recently used (LRU) cache replacement algorithm with a set of N pointer registers that point to respective ways of an N-way set of memory blocks. One of the pointer registers is an LRU pointer, pointing to a least recently used way and another of the pointer registers is a most recently used (MRU) pointer, pointing to a most recently used way. For a cache fill operation in which a new memory block is written to one of the N ways, the new memory block is written into the way (wayn) pointed to by the LRU pointer. All the pointers except the MRU pointer are promoted to point to a way pointed to by respective newer neighboring pointers, the newer neighboring pointers being neighbors toward the MRU pointer.
U.S. Pat. No. 6,347,364 discloses schedulable dynamic memory pinning. An application submits a request for pinning its memory for a certain duration. As compensation, the application may offer other currently mapped pages for replacement. The request may also include the number of pages and the duration of time. The request is granted with the constraint policies which the application is to follow. Such constraint policies include number of pages and length of time the pages may remain pinned in memory. When compensation pages are offered, those pages are replaced in place of the pages which are granted the privilege of being pinned.
U.S. Pat. No. 5,897,660 discloses a method for managing free physical pages that reduces trashing to improve system performance, wherein the claimed invention overcomes the drawbacks of conventional operating system implementations of virtual to physical memory address mapping by providing a method for free physical page management and translation of virtual addresses to physical addresses that increase the effectiveness of the cache memory by reducing the thrashing caused by unfavorable mapping of virtual to physical addresses.
U.S. Pat. No. 5,809,563 discloses a method and apparatus for translating a virtual address into a physical address in a multiple region virtual memory environment. A translation lookaside buffer (TLB) is configured to provide page table entries to build a physical address. The TLB is supplemented with a virtual hash page table (VHPT) to provide TLB entries in the occurrence of TLB misses.
Transaction systems prefetch pages in anticipation of these pages being referenced in the future. Current systems would prefetch pages that are in some multiple of pages adjacent to the current one being processed. Other mechanisms include using an index which forms an ordered list of page references, which can be used to prefetch pages to be examined. The following references provide for a general teaching with regard to prefetching, but they fail to provide for the claimed invention's robust method and system of prefetching in ordered nodes wherein the nodes are ordered into isolated regions.
U.S. patent application publication 2002/0103778 discloses a method and system for adaptive prefetching. A cache server may prefetch one or more web pages from an origin server prior to those web pages being requested by a user. The cache server determines which web pages to prefetch based on a graph associated with a prefetch module associated with the cache server. The graph represents all or a portion of the web pages at the origin server using one or more nodes and one or more links connecting the nodes. Each link has an associated transaction weight and user weight.
U.S. patent application publication 2002/0078165 discloses a system and method for prefetching portions of a web page based on learned preferences. A system and a method for prefetching portions of a web page is based on preferences learned from previous visits to the web page. The disclosed prefetching technique determines whether a user prefers certain sub-pages of the web page and, if so, prefetches these preferred sub-pages prior to the other sub-pages of the web page. The set of preferred sub-pages is generated by analyzing the user's actions during previous visits to the web page.
U.S. Pat. No. 6,385,641 discloses an adaptive prefetching method for use in a computer network and web browsing. The prefetching scheme consists of two modules: a prediction module and a threshold module. After a user's request for a new file is satisfied, the prediction module immediately updates a database of history information, if needed, and computes the access probability for each candidate file where the access probability of a file is an estimate of the probability with which that file will be requested by the user in the near future. Next, the threshold module determines the prefetch threshold for each related server which contains at least one candidate file with nonzero access probability. The threshold is determined in real time based on then current network conditions. Finally, each file whose access probability exceeds or equals its server's prefetch threshold is prefetched. When prefetching a file, the file is actually downloaded if and only if no up-to-date version of the file is available on the local computer; otherwise, no action is taken.
U.S. Pat. No. 6,085,193 discloses a method and system for dynamically prefetching information via a server hierarchy. The method for prefetching data identifies data access patterns and prefetches select information based on dynamic interpretation of the data access patterns. The content server or proxy server identifies data access reference patterns of clients associated with the content server or the proxy server hierarchy. The decision to prefetch select information for the clients is made based on prefetch hint information and prefetch hint values.
U.S. Pat. No. 6,081,799 discloses a method for executing complex SQL queries using index screening for conjunct or disjunct index operations. A query is executed to access data stored on a data storage device connected to a computer. In particular, while accessing one or more indexes to retrieve row identifiers, index matching predicates in the query are applied to select row identifiers and index screening predicates in the query are applied to eliminate one or more selected row identifiers.
U.S. Pat. No. 6,067,565 discloses a technique for prefetching a web page of potential future interest in lieu of continuing a current information download. Described within is a technique that, through continual computation, harnesses available computer resources during periods of low processing activity and low network activity, such as idle time, for prefetching, e.g., web pages or pre-selected portions thereof, into the local cache of a client computer.
U.S. Pat. No. 6,026,474 discloses shared client-side web caching using globally addressable memory. A shared client-side Web cache is provided by implementing a file system shared between nodes. Each browser application stores cached data in files stored in a globally addressable data store. Since the file system is shared, the client-side Web caches are also shared.
Whatever the precise merits, features, and advantages of the above-cited references, none of them achieves or fulfills the purposes of the present invention.